<?php

namespace App\Http\Controllers\v1\algorithmAndDataStruct;

/**
 * 二叉树
 *
 */
class TreeNode
{
    public $val = 0;
    public $left = null;
    public $right = null;
    public $result = [];
    public function __construct($val = 0, $left = null, $right = null)
    {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }

    /**
     * 中序遍历 左中右
     * @param $rootNode
     * @return array
     */
    public function inorderTraversal($currentNode): array
    {
        $stack = $result = [];
//        $currentNode = $rootNode;
        while ($currentNode != null || count($stack) > 0) {
            if ($currentNode) {
                $stack[] = $currentNode;
                $currentNode = $currentNode->left;//左子树遍历完
            } else {
                $currentNode = array_pop($stack);
                $result[] = $currentNode->val;
                $currentNode = $currentNode->right;//开始遍历右子树
            }
        }
        return $result;
    }

    /**
     * 递归中序遍历
     * @param $rootNode
     * @return array|mixed
     */
    public function recurrenceInorderTraversal($rootNode)
    {
        if ($rootNode) {
            $this->recurrenceInorderTraversal($rootNode->left);
            $this->result[] = $rootNode->val;
            $this->recurrenceInorderTraversal($rootNode->right);
        }
        return $this->result;
    }

    /**
     * 前序遍历 中左右
     * @param $rootNode
     * @return array
     */
    public function prevTraversal($rootNode): array
    {
        $stack = $result = [];
        $stack[] = $rootNode;
        while (count($stack) > 0) {
            if ($rootNode) {
                $rootNode = array_pop($stack);
                $result[] = $rootNode->val;//中
                if ($rootNode->right) {//先入栈，后出
                    $stack[] = $rootNode->right;
                }
                if ($rootNode->left) {//后入栈，先出
                    $stack[] = $rootNode->left;
                }
            }
        }
        return $result;
    }

    /**
     * 后序遍历 左右中
     * @param $rootNode
     * @return array
     */
    public function postorderReversal($rootNode): array
    {
        $stack = $result = [];
        $stack[] = $rootNode;
        //中右左
        while (count($stack) > 0) {
            $rootNode = array_pop($stack);
            $result[] = $rootNode->val;//中
            if ($rootNode->left) {//先入栈，后出
                $stack[] = $rootNode->left;
            }
            if ($rootNode->right) {//后入栈，先出
                $stack[] = $rootNode->right;
            }
        }
        //左右中
        return array_reverse($result);
    }

}